#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution
{
public:
	std::vector<Interval> insert(std::vector<Interval>& intervals, Interval newInterval)
	{
		std::map<int, int> headMap;
		std::map<int, int> tailMap;
		for (int i = 0; i < intervals.size(); i++) {
			headMap[intervals[i].start] = i;
			tailMap[intervals[i].end] = i;
		}
		auto head = tailMap.lower_bound(newInterval.start);
		auto tail = headMap.upper_bound(newInterval.end);
		if (head == tailMap.end()) {
			std::cout << "case1" << std::endl;
			intervals.emplace_back(newInterval);
		}else if (tail != headMap.end() && tail->second == 0 && newInterval.end < intervals[0].start) {
			std::cout << "case2" << std::endl;
			intervals.emplace_back(newInterval);
		} else {
			std::cout << "case3" << std::endl;
			auto ihead = head->second;
			tail--;
			auto itail = tail->second;
			newInterval.start = std::min(newInterval.start, intervals[ihead].start);
			newInterval.end = std::max(newInterval.end, intervals[itail].end);
			intervals.erase(intervals.begin() + ihead, intervals.begin() + itail + 1);
			intervals.emplace_back(newInterval);
		}
		std::sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2) { return i1.start < i2.start; });
		return intervals;
	}
};

int main()
{
	std::vector<Interval> intervals{ { 1, 2 }, { 3, 5 }, { 6, 7 }, { 8, 10 }, {12, 16} };
	auto result = Solution().insert(intervals, Interval{4, 9});
	system("pause");
	return 0;
}